package code.commonAlgorithm;

import java.util.Arrays;
import java.util.Random;

/**
 * @author 26029
 * @date 2025/4/16
 * @description
 */
public class QuickSort {
    // 快速排序：常规挖坑法
    public static void quickSort(int[] arr, int left, int right) {
        if (left >= right) return; // 递归终止条件：只有一个元素
        // 随机找到一个枢轴并完成一轮划分
        int random = left + new Random().nextInt(right - left + 1);
        swap(arr, right, random);

        int pivot = arr[right];
        int hole = right;
        int l = left, r = right;
        while (l < r) {
            // find arr[l] > pivot
            while (l < r && arr[l] <= pivot)
                l++;
            arr[hole] = arr[l];
            hole = l;
            // find arr[r] < pivot
            while (l < r && arr[r] >= pivot)
                r--;
            arr[hole] = arr[r];
            hole = r;
        }
        arr[hole] = pivot;
        // 递归
        quickSort(arr, left, hole - 1);
        quickSort(arr, hole + 1, right);
    }

    // 快速排序：三路
    private static void quickSort3Way(int[] nums, int left, int right) {
        if (left >= right) return;

        int random = left + new Random().nextInt(right - left + 1);
        int lt = left, gt = right;
        int pivot = nums[random];
        int i = left;

        while (i <= gt) {
            if (nums[i] < pivot) {
                swap(nums, lt, i);
                i++;
                lt++;
            } else if (nums[i] > pivot) {
                swap(nums, i, gt);
                gt--;
            } else {
                i++;
            }
        }

        quickSort3Way(nums, left, lt - 1);
        quickSort3Way(nums, gt + 1, right);
    }

    // 交换两个元素
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    // 主程序
    public static void main(String[] args) {
        int[] arr = {1, 0, 0, 2, 2, 2, 2, 2, 2, 1, 1, 0, 0, 0, 1, 0, 2, 0, 1};
        System.out.println("排序前：" + Arrays.toString(arr));
        quickSort3Way(arr, 0, arr.length - 1); // 调用快速排序
        System.out.println("排序后：" + Arrays.toString(arr));
    }
}
